#include "estructurado.h"
#define NUMERO_MODELOS	9
#define PRIMER_DIGITO	24	
#define SEGUNDO_DIGITO	18
#define K 5//cantidad de bytes de techo y piso
void inicializar_modelo(uint64_t* vector[]){
	int i,j,k;
	vector[0] = (uint64_t*) malloc(sizeof(uint64_t) * 3);
	vector[0][0] = 1;
	vector[0][1] = 1;
	vector[0][2] = 2;
	vector[1]=(uint64_t*)malloc(sizeof(uint64_t) * 3);
	vector[1][0] = 1;
	vector[1][1] = 1;
	vector[1][2] = 2;
	i = 1;
	for (j = 2; j < NUMERO_MODELOS; j++) {
		i *= 2;
		vector[j]=(uint64_t*)malloc(sizeof(uint64_t) * (i+2));
		for (k=0;k<(i+1);k++) {
			vector[j][k] = 1;
		}
		vector [j][i+1] = i+1;
	}
}

void eliminar_modelo (uint64_t* vector[]){
	free(vector[0]);
	free(vector[1]);
	int j; 
	for (j=2; j < NUMERO_MODELOS; j++) 
		free (vector[j]);
}

void normalizar(uint32_t *piso, uint32_t *techo, uint64_t fnum, uint64_t fanteriores, uint64_t fmodelo) {
	(*techo)++;
	uint64_t numerador = (*techo - *piso) * (uint64_t) fanteriores;
	uint32_t piso_nuevo = *piso + numerador / fmodelo;
	numerador = (*techo - *piso) * (uint64_t) (fnum + fanteriores);
	*techo = *piso + numerador / fmodelo - 1;
	*piso = piso_nuevo;
}

void comprobar_tp (uint32_t *piso, uint32_t *techo, unsigned char *resultado, int *numeros_copiados, int *contador_under, uint32_t *piso_under) {
	uint32_t primerd_piso = *piso >> PRIMER_DIGITO;
	uint32_t primerd_techo = *techo >> PRIMER_DIGITO;
	bool cambio_resultado = (primerd_piso == primerd_techo);
	int numero_iteraciones = 0;
	
	// chequeo del underflow
	uint32_t aux = 0;
	aux = (~aux);      
	uint32_t max_num_digito = aux >> (PRIMER_DIGITO + 2);		// seria el "9"
	uint32_t segundod_piso = (*piso << (32 - PRIMER_DIGITO)) >> (PRIMER_DIGITO + 2);
	uint32_t segundod_techo = (*techo << (32 - PRIMER_DIGITO)) >> (PRIMER_DIGITO + 2);
	if (primerd_piso == primerd_techo - 1) {
		*piso_under = primerd_piso;
		while (!(segundod_piso ^ max_num_digito) && segundod_techo == 0) { 
			(*contador_under)++;
			*piso = (primerd_piso << PRIMER_DIGITO)  + ((*piso <<  (32 - SEGUNDO_DIGITO)) >> (32 - PRIMER_DIGITO));
			*techo = (primerd_techo << PRIMER_DIGITO) + ((*techo <<  (32 - SEGUNDO_DIGITO)) >> (32 - PRIMER_DIGITO)) + max_num_digito;
			segundod_piso = (*piso << (32 - PRIMER_DIGITO)) >> (PRIMER_DIGITO + 2);
			segundod_techo = (*techo << (32 - PRIMER_DIGITO)) >> (PRIMER_DIGITO + 2);
		}
	}
	
	//chequeo si los 1ros digitos son iguales
	while (cambio_resultado) {
		numero_iteraciones++;
		resultado[*numeros_copiados] = primerd_piso;
		(*numeros_copiados)++;
		*piso = (*piso << (32 - PRIMER_DIGITO)) >> 2;
		*techo = ((*techo << (32 - PRIMER_DIGITO)) >> 2) + max_num_digito;
		while ((*contador_under) > 0) {
			if (*piso_under == primerd_piso)
				resultado[*numeros_copiados] = max_num_digito;
			else
				resultado[*numeros_copiados] = 0;
			(*numeros_copiados)++;
			(*contador_under)--;
		}
		primerd_piso = *piso >> PRIMER_DIGITO;
		primerd_techo = *techo >> PRIMER_DIGITO;
		cambio_resultado = (primerd_piso == primerd_techo);
	}
}

uint32_t pasar_numero (unsigned char *buffer, int posiciones_corridas, int *largo_buffer){
	int i;
	char* aux = (char*) malloc (sizeof(char) * (K + 1));
	if (posiciones_corridas != 0) {
		for (i = posiciones_corridas; i < *largo_buffer; i++)
			buffer[i - posiciones_corridas] = buffer[i];
	}
	(*largo_buffer) -= posiciones_corridas;
	for (i = 0;  i < K && i < *largo_buffer; i++)
		aux[i] = buffer[i];
	*(aux + K) = '\0';
	uint32_t num = 0;
	uint32_t num_aux;
	for (i = 0; i < K && i < *largo_buffer; i++) {
		num_aux = aux[i];
		num = num + (num_aux << (PRIMER_DIGITO - (PRIMER_DIGITO - SEGUNDO_DIGITO) * i));
	}
	free (aux);
	return num;
}

void comprobar_tp_descomp (uint32_t *piso, uint32_t *techo, unsigned char *buffer, uint32_t *numero, int *largo_buffer) {
	uint32_t primerd_piso = *piso >> PRIMER_DIGITO;
	uint32_t primerd_techo = *techo >> PRIMER_DIGITO;
	bool cambio_resultado = (primerd_piso == primerd_techo);
	int numero_iteraciones = 0;
	bool elimino_digito = false;
	int cant_digitos_eliminados = 0;
	
	// chequeo del underflow
	uint32_t aux = 0;
	aux = (~aux);      
	uint32_t max_num_digito = aux >> (PRIMER_DIGITO + 2);		// seria el "9"
	uint32_t segundod_piso = (*piso << (32 - PRIMER_DIGITO)) >> (PRIMER_DIGITO + 2);
	uint32_t segundod_techo = (*techo << (32 - PRIMER_DIGITO)) >> (PRIMER_DIGITO + 2);
	if (primerd_piso == primerd_techo - 1) {
		while (!(segundod_piso ^ max_num_digito) && segundod_techo == 0) { 
			elimino_digito = true;
			cant_digitos_eliminados++;
			*piso = (primerd_piso << PRIMER_DIGITO)  + ((*piso <<  (32 - SEGUNDO_DIGITO)) >> (32 - PRIMER_DIGITO));
			*techo = (primerd_techo << PRIMER_DIGITO) + ((*techo <<  (32 - SEGUNDO_DIGITO)) >> (32 - PRIMER_DIGITO)) + max_num_digito;
			segundod_piso = (*piso << (32 - PRIMER_DIGITO)) >> (PRIMER_DIGITO + 2);
			segundod_techo = (*techo << (32 - PRIMER_DIGITO)) >> (PRIMER_DIGITO + 2);
		}
	}
	while (cambio_resultado) {
		numero_iteraciones++;
		*piso = (*piso << (32 - PRIMER_DIGITO)) >> 2;
		*techo = ((*techo << (32 - PRIMER_DIGITO)) >> 2) + max_num_digito;
		primerd_piso = *piso >> PRIMER_DIGITO;
		primerd_techo = *techo >> PRIMER_DIGITO;
		cambio_resultado = (primerd_piso == primerd_techo);
	}	
	if (numero_iteraciones != 0)
		*numero = pasar_numero(buffer, numero_iteraciones, largo_buffer);
	if (elimino_digito) {
		int i;
		unsigned char aux = 0;
		for (i = 0; i < cant_digitos_eliminados; i++) {
			uint32_t resto = (*numero << (32 - SEGUNDO_DIGITO)) >> (32 - PRIMER_DIGITO);
			aux = buffer[i + K];
			*numero = ((*numero >> PRIMER_DIGITO) << PRIMER_DIGITO) + resto + aux;
		}
		int j;
		for (j = cant_digitos_eliminados + 1; j < *largo_buffer; j++)
			buffer[j - cant_digitos_eliminados] = buffer[j];
		(*largo_buffer) -= cant_digitos_eliminados;
	}
}

void analizar_numero (uint32_t numero, uint64_t* vector[], uint32_t *piso, uint32_t *techo, unsigned char *resultado, int *numeros_copiados, int *contador_under, uint32_t *piso_under){
	bool terminar = false;
	int posicion; //ubicacion del caracter a analizar
	int ultima_posicion; //posicion de las frecuencias totales del modelo
	int nivel = 0;
	uint32_t suma;
	
	//analizar modelo 0
	ultima_posicion = 2;
	if (numero == 0) {
		posicion = 0;
		terminar = true;
	}
	else
		posicion = 1; //lugar del escape
		
	//cambio modelo 0
	suma = 0;
	int i;
	for (i = 0; i < posicion; i++)
		suma = suma + vector [nivel][i];
	normalizar(piso, techo, vector[nivel][posicion], suma, vector[nivel][ultima_posicion]);
	comprobar_tp(piso, techo, resultado, numeros_copiados, contador_under, piso_under);
	vector[nivel][posicion]++;
	vector[nivel][ultima_posicion]++;//posicion de f del modelo
	
	if (terminar) return; //si era 0 termine
	//analizar modelo 1
	nivel = 1;
	if (numero == 1) {
		posicion = 0;
		terminar = true;
	}

	suma = 0;
	for (i=0; i < posicion; i++)
		suma = suma + vector [nivel][i];
	normalizar(piso, techo, vector[nivel][posicion],suma,vector[nivel][ultima_posicion]);
	comprobar_tp(piso, techo, resultado, numeros_copiados, contador_under, piso_under);
	vector[nivel][posicion]++;
	vector[nivel][ultima_posicion]++;
	if (terminar) return;

	int piso_nivel = pow ( 2 , (nivel-1));
	int techo_nivel = pow (2, (nivel)) - 1;
	while (!terminar) {
		nivel ++;
		piso_nivel *= 2;
		techo_nivel = (techo_nivel + 1) * 2 - 1;
		ultima_posicion = (techo_nivel - piso_nivel) + 2;
		if ((piso_nivel <= numero) && (numero <= techo_nivel)) {
			terminar = true;
			posicion = numero - piso_nivel;
		}else
			posicion = ultima_posicion - 1; //uno menos q las frecuencias totales del modelo
		suma = 0;
		for (i=0; i < posicion; i++)
			suma = suma + vector [nivel][i];
		normalizar(piso, techo, vector[nivel][posicion],suma,vector[nivel][ultima_posicion]);
		comprobar_tp(piso, techo, resultado, numeros_copiados, contador_under, piso_under);
		vector[nivel][posicion]++;
		vector[nivel][ultima_posicion]++;
	}	
}

bool comprimir_estructurado(tcola cola, unsigned char *resultado, int *tamanio_resultado) {
	uint64_t* vector [NUMERO_MODELOS];
	inicializar_modelo(vector);
	uint32_t piso = 0;
	uint32_t techo = 0;
	techo = ~techo >> 2;				// ver cual es el rango maximo con que funciona
	unsigned char *baux = (unsigned char*) malloc (sizeof(char) * TAMANIOBUFFER * 2);
	unsigned char *aux = (unsigned char*) malloc (sizeof(char) * 20);
	int numeros_copiados = 0;
	int contador_under = 0;
	uint32_t piso_under = 0;
	int j;
	int tamanio_buffer_final = 0;
	while (!cola_vacia(cola)) {
		unsigned char *dato;
		borrar_cola(&cola, (tdatoc*) &dato);
		analizar_numero(*dato, vector, &piso, &techo, aux, &numeros_copiados, &contador_under, &piso_under);
		for(j = 0; j < numeros_copiados; j++) {
			baux[tamanio_buffer_final] = aux[j];
			tamanio_buffer_final++;
		}
		numeros_copiados = 0;
		free(dato);
	}
	//acomodo techo y piso para que solo esten iguales en el primer digito de 6 bits
	uint32_t resto_de_unos = 255;
	resto_de_unos = ~(resto_de_unos << PRIMER_DIGITO);
	techo = ((techo >> PRIMER_DIGITO) << PRIMER_DIGITO) + resto_de_unos;
	piso = techo;
	piso = (piso >> PRIMER_DIGITO) << PRIMER_DIGITO;
	comprobar_tp (&piso, &techo, baux, &tamanio_buffer_final, &contador_under, &piso_under);
	
	// agarramos de a 4 bytes de 6 bits para transformarlos en 3 bytes de 8 bits
	uint8_t primerCaracter;
	uint8_t segundoCaracter;
	uint8_t tercerCaracter;
	j = 0;
	int k = 0;
	int iteraciones  = (tamanio_buffer_final >> 2) << 2;
	while(j < iteraciones) {
		primerCaracter = (baux[j] << 2) + ((unsigned char) baux[j + 1] >> 4);
		segundoCaracter = (baux[j + 1] << 4) + ((unsigned char) baux[j + 2] >> 2);
		tercerCaracter = (baux[j + 2] << 6) + (baux[j + 3]);
		resultado[k] = primerCaracter;
		resultado[k + 1] = segundoCaracter;
		resultado[k + 2] = tercerCaracter;
		k +=3;
		j += 4;
	}
	*tamanio_resultado =  (iteraciones * 3) / 4;
	switch (tamanio_buffer_final - iteraciones)
	{
		case 1: 
			primerCaracter = baux[iteraciones] << 2;
			resultado[k] = primerCaracter;
			(*tamanio_resultado) += 1;
			break;
		case 2:
			primerCaracter = (baux[iteraciones] << 2) + ((unsigned char) baux[iteraciones + 1] >> 4);
			segundoCaracter = (baux[iteraciones + 1] << 4);
			resultado[k] = primerCaracter;
			resultado[k + 1] = segundoCaracter;
			(*tamanio_resultado) += 2;
			break;
		case 3:
			primerCaracter = (baux[iteraciones] << 2) + ((unsigned char) baux[iteraciones + 1] >> 4);
			segundoCaracter = (baux[iteraciones + 1] << 4) + ((unsigned char) baux[iteraciones + 2] >> 2);
			tercerCaracter = (baux[j + 2] << 6);
			resultado[k] = primerCaracter;
			resultado[k + 1] = segundoCaracter;
			resultado[k + 2] = tercerCaracter;
			(*tamanio_resultado) += 3;
			break;
	}
	eliminar_modelo (vector);
	free (baux);
	free (aux);
	return true;
}



int calcular_numero (int nivel, int posicion){
	if ((nivel == 0)||(nivel ==1))
		return nivel;
	int piso_nivel = pow (2, (nivel-1));
	return (piso_nivel + posicion);
}

int analizar_numero_descomprimir (unsigned char* buffer, uint64_t* vector[], uint32_t *piso, uint32_t *techo, int *largo_buffer) {
	bool terminar = false;
	int posicion; //ubicacion del caracter a analizar
	int ultima_posicion; //posicion de las frecuencias totales del modelo
	int nivel = 0;
	uint64_t suma;
	//analizar modelo 0
	ultima_posicion = 2;
	uint32_t numero = pasar_numero (buffer, 0, largo_buffer);
	posicion = 0;
	uint64_t numerador = (*techo - *piso + 1) * (uint64_t) vector[nivel][posicion];
	uint32_t peso = *piso + numerador / vector[nivel][ultima_posicion] - 1;
	if (numero <= peso) {
		posicion = 0;
		terminar = true;
	}
	else
		posicion = 1; //lugar del escape
	//cambio modelo 0
	suma = 0;
	int i;
	for (i = 0; i < posicion; i++)
		suma = suma + vector [nivel][i];
	normalizar(piso, techo, vector[nivel][posicion],suma, vector[nivel][ultima_posicion]);
	comprobar_tp_descomp(piso, techo, buffer, &numero, largo_buffer);
	
	vector[nivel][posicion]++;
	vector[nivel][ultima_posicion]++;//posicion de f del modelo
	
	if (terminar)
		return calcular_numero (nivel, posicion); //si era 0 termine
	//analizar modelo 1
	nivel = 1;
	posicion = 0;
	numerador = (*techo - *piso + 1) * (uint64_t) vector[nivel][posicion];
	peso = *piso + numerador / vector[nivel][ultima_posicion] - 1;
	if (numero <= peso) {
		posicion = 0;
		terminar = true;
	} 
	else
		posicion = 1;
	suma = 0;
	for (i=0; i < posicion; i++)
		suma = suma + vector [nivel][i];
	normalizar(piso, techo, vector[nivel][posicion], suma, vector[nivel][ultima_posicion]);
	comprobar_tp_descomp(piso, techo, buffer, &numero, largo_buffer);
	vector[nivel][posicion]++;
	vector[nivel][ultima_posicion]++;

	if (terminar)
		return calcular_numero (nivel, posicion); //si era 1 termine
	while (!terminar) {
		if (numero > *techo) {
			printf ("numero fuera del intervalo techo piso \n");
			exit(-1);
		}
		nivel++;
		posicion = 0;
		int piso_nivel = pow (2 , nivel - 1);
		int techo_nivel = pow (2, nivel) - 1;
		ultima_posicion = (techo_nivel - piso_nivel) + 2;
		bool encontre = false;
		while (!encontre) {
			suma = 0;
			for (i = 0; i <= posicion; i++)
				suma = suma + vector [nivel][i];
			numerador = (*techo - *piso + 1) * (uint64_t) suma;
			peso = *piso + numerador / vector[nivel][ultima_posicion] - 1;
			
			if (numero <= peso)
				encontre = true;
			else
				posicion++;
			if (posicion == ultima_posicion) {
				printf("ouch\n");
				encontre = true;
				posicion--;
			}
		}
		if (posicion != ultima_posicion - 1) 
			terminar = true;
		
		suma = 0;
		for (i = 0; i < posicion; i++)
			suma = suma + vector [nivel][i];
		normalizar(piso, techo, vector[nivel][posicion], suma, vector[nivel][ultima_posicion]);
		comprobar_tp_descomp(piso, techo, buffer, &numero, largo_buffer);
		vector[nivel][posicion]++;
		vector[nivel][ultima_posicion]++;
		if (terminar) 
			return calcular_numero (nivel, posicion);
	}	
	return  calcular_numero (nivel, posicion);
}


bool descomprimir_estructurado (unsigned char *buffer_original, tcola *cola, int tamanio_resultado, int tam_arch_orig) {
	uint64_t* vector [NUMERO_MODELOS];
	inicializar_modelo(vector);
	uint32_t piso = 0;
	uint32_t techo = 0;
	techo = (~techo) >> 2;
	unsigned char* buffer = (unsigned char*) malloc (sizeof(char) * TAMANIOBUFFER + 2);
	int j = 0;
	int iteraciones  = (tamanio_resultado / 3) * 3;
	// agarramos de a 4 bytes de 6 bits para transformarlos en 3 bytes de 8 bits
	uint8_t primerCaracter;
	uint8_t segundoCaracter;
	uint8_t tercerCaracter;
	uint8_t cuartoCaracter;
	int k = 0;
	while(j < iteraciones) {
		primerCaracter = ((unsigned char) buffer_original[j] >> 2);
		segundoCaracter = (((unsigned char)(buffer_original[j] << 6)) >> 2) + ((unsigned char) buffer_original[j + 1] >> 4);
		tercerCaracter = (((unsigned char)(buffer_original[j + 1] << 4) >> 2)) + ((unsigned char) buffer_original[j + 2] >> 6);
		cuartoCaracter = (unsigned char)(buffer_original[j + 2] << 2) >> 2;
		buffer[k] = primerCaracter;
		buffer[k + 1] = segundoCaracter;
		buffer[k + 2] = tercerCaracter;
		buffer[k + 3] = cuartoCaracter;
		k += 4;
		j += 3;
	}
	switch (tamanio_resultado - iteraciones)
	{
		case 0:
			if (cuartoCaracter == 0)
				k--;
			break;
		case 1: 
			primerCaracter = (unsigned char)buffer_original[iteraciones] >> 2;
			segundoCaracter = (unsigned char)(buffer_original[iteraciones] << 6) >> 2;
			buffer[k] = primerCaracter;
			if (segundoCaracter != 0) {
				buffer[k + 1] = segundoCaracter;
				k += 1;
			}
			k += 1;
			break;
		case 2:
			primerCaracter = (unsigned char)buffer_original[iteraciones] >> 2;
			segundoCaracter = ((unsigned char)(buffer_original[iteraciones] << 6) >> 2) + ((unsigned char) buffer_original[iteraciones + 1] >> 4);
			tercerCaracter = (((unsigned char)(buffer_original[iteraciones + 1] << 4) >> 2));
			buffer[k] = primerCaracter;
			if (tercerCaracter != 0) {
				buffer[k + 2] = tercerCaracter;
				k += 1;
			}
			if (segundoCaracter != 0) {
				buffer[k + 1] = segundoCaracter;
				k += 1;
			}else if (tercerCaracter != 0) {
				buffer[k + 1] = segundoCaracter;
				k += 1;
			}
			
			k += 1;
			break;
	}
	int largo_buffer = k;
	k = 0;
	while (k < tam_arch_orig) {
		uint8_t num = analizar_numero_descomprimir (buffer, vector, &piso, &techo, &largo_buffer);
		unsigned char *dato = (unsigned char*) malloc (sizeof(char));
		*dato = num;
		insertar_cola(cola, dato);
		k++;
	}	
	free (buffer);
	eliminar_modelo (vector);
	return true;
}


